package com.loriot.common.points_that_intersect_with_cars_2848;

import java.util.List;

/**
 * @Title: pointsThatIntersectWithCars_2848
 * @Package: com.loriot.common
 * @Description:
 * @Author: zzy boy
 * @Date: 2025/10/21 10:36
 * @Version: 0.0.1-alpha
 */

public class Main {
    class Solution1 {
        // 数数方法
        public int numberOfPoints(List<List<Integer>> nums) {
            int size = 0;
            for(List<Integer> item:nums)size = size>item.get(1)?size:item.get(1);
            int[] tag = new int[size];
            int count = 0;
            for(List<Integer> item: nums){
                int start = item.get(0)-1;
                int end = item.get(1);
                for(int i=start;i<end;i++){
                    if(tag[i]!=1){
                        tag[i] = 1;
                        count++;
                    }
                }
            }

            return count;

        }
    }

    class Solution2 {
        // 差分方法
        public int numberOfPoints(List<List<Integer>> nums) {
            int size = 0;
            for(List<Integer> item:nums)size = size>item.get(1)?size:item.get(1);
            // 注意这里应该是size+1，因为尾部的标记不是-1，尾部+1的的标记才是-1
            // 直到尾都存在车辆，只有尾的下一个位置没有车辆
            int[] tag = new int[size+1];
            for(List<Integer> item: nums){
                tag[item.get(0)-1] += 1;
                tag[ item.get(1)] += -1;
            }
            int difference = 0;
            int count = 0;
            for(int i=0;i<size+1;i++){
                difference += tag[i];
                if(difference>0){
                    count++;
                }
            }

            return count;

        }
    }
}
